<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>

  <body>
    <script>
      var reverseBetween = function (head, left, right) {
        // 方法一：使用数组暴力反转之后再赋值给原来的链表（）---时间：O（3n）（）---空间：O（n）（数组）
        // const arr = [];
        // let list1 = head;
        // let list2 = head;
        // while (list1) {
        //   arr.push(list1.val);
        //   list1 = list1.next;
        // }
        // while (left < right) {
        //   let temp = arr[left - 1];
        //   arr[left - 1] = arr[right - 1];
        //   arr[right - 1] = temp;
        //   left++;
        //   right--;
        // }
        // while (list2) {
        //   list2.val = arr.shift();
        //   list2 = list2.next;
        // }
        // return head;

        // 反转前n个节点，递归
        // 记住n+1个节点，反转完之后head得指向这个节点
        // let temp = null
        // function reverseN(head,n){
        //   if(n===1){
        //     temp = head.next
        //     return head;
        //   }
        //   // newHead 为反转之后的头节点,并且一直没变
        //   let newHead = reverseN(head.next,n-1)
        //   head.next.next = head;
        //   head.next = temp;
        //   return newHead;
        // }

        // 反转前n个节点，迭代
        // function reverseN(head, n) {
        //   let pre = null;
        //   let cur = head;
        //   for(let i = 0; i < n; i++) {
        //     let temp = cur.next;
        //     cur.next = pre;
        //     pre = cur;
        //     cur = temp;
        //   }
        //   head.next = cur;
        //   return pre;
        // }

        // 方法二：使用递归（）---时间：O（n或者n^2）（栈空间）---空间：O（1）（）
        // if(left===1){
        //   return reverseN(head,right)
        // }
        // head.next = reverseBetween(head.next,left-1,right-1);
        // return head;

        // 方法三：使用使用迭代（自己想的）---时间：O（）（栈空间）---空间：O（1）（）
        // let tempHead = new ListNode(0);
        // // 符合测试用例
        // // let tempHead = {}
        // let tempHeadP = tempHead;
        // let tempFotter = null;
        // function reverseN(head, n) {
        //   if (n === left) {
        //     tempFotter = head.next;
        //     return head;
        //   }
        //   // newHead 为反转之后的头节点,并且一直没变
        //   let newHead = reverseN(head.next, n - 1);
        //   head.next.next = head;
        //   head.next = tempFotter;
        //   return newHead;
        // }
        // let i = 1;
        // while (left < right && i < left) {
        //     tempHead.val = head.val;
        //     // tempHead.next = {};
        //     tempHead.next =  new ListNode(0);
        //     if(i!==left-1){
        //       tempHead = tempHead.next;
        //     }
        //   head = head.next;
        //   i++;
        // }
        // if(tempHead.next){
        //   tempHead.next = reverseN(head, right);
        //   return tempHeadP;
        // }else{
        //   return reverseN(head, right);
        // }

        // 方法四：使用迭代（自己想的）---时间：O（N）（）---空间：O（1）（）
        // let tempHead = new ListNode(0);
        // 符合测试用例
        // let tempHead = {}
        // let tempHeadP = tempHead;
        // function reverseN(head, n) {
        //   let pre = null;
        //   let cur = head;
        //   for(let i = 0; i < n; i++) {
        //     let temp = cur.next;
        //     cur.next = pre;
        //     pre = cur;
        //     cur = temp;
        //   }
        //   head.next = cur;
        //   return pre;
        // }
        // let i = 1;
        // while (left < right && i < left) {
        //     tempHead.val = head.val;
        //     tempHead.next = {};
        //     // tempHead.next =  new ListNode(0);
        //     if(i!==left-1){
        //       tempHead = tempHead.next;
        //     }
        //   head = head.next;
        //   i++;
        // }
        // if(tempHead.next){
        //   tempHead.next = reverseN(head, right-left+1);
        //   return tempHeadP;
        // }else{
        //   return reverseN(head, right-left+1);
        // }

        // 方法五：使用迭代（官方）---时间：O（N）（遍历整个链表）---空间：O（1）（）
        // function reverseN(head) {
        //   let prev = null;
        //   let cur = head;
        //   while (cur) {
        //     let temp = cur.next;
        //     cur.next = prev;
        //     prev = cur;
        //     cur = temp;
        //   }
        //   return prev;
        // }
        // let list = new ListNode(-1);
        // list.next = head;
        // let tempLeft = list;
        // // 开始节点的前一个节点
        // for (let i = 0; i < left - 1; i++) {
        //   tempLeft = tempLeft.next;
        // }
        // // 反转链表的最后一个节点
        // let tempRight = tempLeft;
        // for (let i = 0; i < right - left + 1; i++) {
        //   tempRight = tempRight.next;
        // }
        // // 切出反转的部分
        // let reverseList = tempLeft.next;
        // // 记录尾连接的开始节点
        // let footerList = tempRight.next;
        // // 切断连接
        // tempLeft.next = null;
        // tempRight.next = null;
        // // 反转
        // // reverseN(reverseList);
        // // 接上
        // // tempLeft.next = tempRight;
        // // 另一种写法
        // // 反转
        // let reverseListTemp = reverseN(reverseList);
        // // 接上
        // tempLeft.next = reverseListTemp;
        // reverseList.next = footerList;
        // return list.next;

        // 方法六：穿针引线头插法（官方）---时间：O（N）（遍历整个链表）---空间：O（1）（）
        // let list = new ListNode(-1);
        // let list = {}
        // list.next = head;
        // // 这里不能等于head，不然还得考虑特殊情况，就算改成left-2也不行
        // let prev = list;
        // for (let i = 0; i < left - 1; i++) {
        //   prev = prev.next;
        // }
        // let curr = prev.next;
        // for (let i = 0; i < right - left; i++) {
        //   const next = curr.next;
        //   curr.next = next.next;
        //   next.next = prev.next;
        //   prev.next = next;
        // }
        // return list.next;

        // 改造上面自己研究的两个方法
        let list = new ListNode(0);
        // let list = {}
        list.next = head;
        let leftHead = list
        function reverseN(head, n) {
          let pre = null;
          let cur = head;
          for(let i = 0; i < n; i++) {
            let temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
          }
          head.next = cur;
          return pre;
        }
        for(let i = 0; i < left-1; i++) {
          leftHead = leftHead.next;
        }
        leftHead.next = reverseN(leftHead.next, right-left+1);
        return list.next;
      };

      const obj = {
        val: 1,
        next: {
          val: 2,
          next: {
            val: 3,
            next: {
              val: 4,
              next: {
                val: 5,
                next: null,
              },
            },
          },
        },
      };
      // console.log(reverseBetween(obj, 1, 4));
      console.log(reverseBetween(obj, 2, 4));
      // console.log(reverseBetween(obj, 3, 4));

      // const obj = {
      //   val: 1,
      //   next: {
      //     val: 2,
      //     next: {
      //       val: 3,
      //       next: null,
      //     },
      //   },
      // };
      // console.log(reverseBetween(obj, 3, 3));

      // const obj = {
      //   val: 3,
      //   next: {
      //     val: 4,
      //     next: null,
      //   },
      // };
      // console.log(reverseBetween(obj, 1, 2));
    </script>
  </body>
</html>
